import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86186
 * Date: 2023-07-31
 * Time: 20:37
 */
public class Test {
    public List<String> buildArray(int[] target, int n) {
        List<String> list = new ArrayList<>();
        if(target.length == 0) return list;
        int i = 1;
        int index = 0;
        while(index < target.length && i <= n) {
            if(target[index] != i) {
                while(index < target.length && target[index] != i && i <= n) {
                    list.add("Push");
                    list.add("Pop");
                    i++;
                }
            }else {
                while(index < target.length && target[index] == i && i <= n) {
                    list.add("Push");
                    index++;
                    i++;
                }
            }
        }

        return list;
    }

    public int[] nextGreaterElement1(int[] nums1, int[] nums2) {
        int[] ret = new int[nums1.length];
        Map<Integer,Integer> hashMap = new HashMap<>();
        for(int i = 0; i < nums2.length; i++) {
            for(int j = i + 1; j < nums2.length; j++) {
                if(nums2[j] > nums2[i]) {
                    hashMap.put(nums2[i],nums2[j]);
                    break;
                }
            }
            if(hashMap.get(nums2[i]) == null) {
                hashMap.put(nums2[i],-1);
            }
        }
        for(int i = 0; i < nums1.length; i++) {
            ret[i] = hashMap.get(nums1[i]);
        }

        return ret;
    }

    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int leng1 = nums1.length;
        int leng2 = nums2.length;
        int[] ret = new int[leng1];
        Map<Integer,Integer> hashMap = new HashMap<>();
        Stack<Integer> stack = new Stack<>();
        for(int i = leng2-1; i >= 0; i--) {
            if(stack.isEmpty()) {
                hashMap.put(nums2[i],-1);
                stack.push(i);
                continue;
            }
            int index = stack.peek();
            if(nums2[i] >= nums2[index]) {
                while(nums2[i] >= nums2[stack.peek()]) {
                    stack.pop();
                    if(stack.isEmpty()) {
                        hashMap.put(nums2[i],-1);
                        break;
                    }
                }
                if(hashMap.get(nums2[i]) == null) {
                    hashMap.put(nums2[i],nums2[stack.peek()]);
                }
                stack.push(i);
            }else {
                hashMap.put(nums2[i],nums2[stack.peek()]);
                stack.push(i);
            }
        }
        for(int i = 0; i < leng1; i++) {
            ret[i] = hashMap.get(nums1[i]);
        }

        return ret;
    }
}
